#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int left, int mid, int right)
{
    int i = left, j = mid + 1, k = 0;
    int* res = (int*)malloc((right - left + 1) * sizeof(int));
    for(; i < mid + 1 && j < right + 1;)
    {
        if(arr[i] < arr[j])
        {
            res[k] = arr[i];
            k++;
            i++;
        }
        else
        {
            res[k] = arr[j];
            k++;
            j++;
        }
    }
    for(; i < mid + 1; i++, k++) res[k] = arr[i];
    for(; j < right + 1; j++, k++) res[k] = arr[j];
    memcpy(arr + left, res, (right - left + 1) * sizeof(int));
    free(res);
}

void mergeSort(int arr[], int left, int right)
{
    if(left >= right || !arr) return;
    int mid = (left + right) / 2;
    
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    
    merge(arr, left, mid, right);
}

void isSorted(int arr[], int N)
{
    for(int i = 0; i < N - 1; i++)
    {
        if(arr[i] > arr[i + 1])
        {
            printf("Not sorted.\n");
            return;
        }
    }
    printf("Sorted.\n");
}

int main()
{
    srand(time(NULL));
    int N = 1000;
    int* arr = (int*)malloc(N * sizeof(int));
    for(int i = 0; i < N; i++)
    {
        arr[i] = rand();
    }
    mergeSort(arr, 0, N - 1);
    isSorted(arr, N);
    free(arr);
    return 0;
}
